What's the Logarithm?
What's the Base of the Logarithm?

	log[B]N = K if B^K = N


What logarithm bases are interesting in Computer Science?

	Base 2
	Base 10


Three simple ways to approximate log(N)

	1. How many digits are needed to represent N?

	2. Repeated halving principle.
	   How many times you can halve N before you get 1 or less?

	3. Repeated doubling principle.
	   Start with X = 1.
	   How many times you can double X before you get N or more?


Give the approximate value of the log base 10 for each number.

	1000
	5000
	9999


Give the approximate value of the log base 2 for each number.

	16
	256
	100



When logarithms are used in Big-Oh formula's,
why is the Big-Oh not affected by the base of the logarithm?

How does the number of digits in a decimal number compare to 
the number of digits in an equivalent binary number?



What's the Big-Oh bound on the following loop?

	for ( int x = 1; x < n; x *= 2 )
	    sum++;



Is O(log N) closer to O(1), closer to O(N), or somewhere in the
middle?


Is O(N log N) closer to O(N), closer to O(N^2), or somewhere in the
middle?